#include<iostream>
#include<cstdlib>
#include<algorithm>
#include<vector>
#include<string>
using namespace std;

class Solution {
    /*背包法 动态规划*/
public:
    int coinChange(vector<int>& coins, int amount) {
        vector<int> dp(amount + 1, INT_MAX);
        dp[0] = 0;
        for (int i = 0; i < coins.size(); i++) { // 遍历物品
            for (int j = coins[i]; j <= amount; j++) { // 遍历背包
                if (dp[j - coins[i]] != INT_MAX) { // 如果dp[j - coins[i]]是初始值则跳过
                    dp[j] = min(dp[j - coins[i]] + 1, dp[j]);
                }
            }
        }
        if (dp[amount] == INT_MAX) return -1;
        return dp[amount];
    }
};

class Solution002 {
    /*动态规划，公式法：f(n) = min(f(n - c1), f(n - c2), ... f(n - cn)) + 1 */
public:
    int coinChange(vector<int>& coins, int amount) {
        vector<int> res(amount + 1, 0);
        for (int i = 1; i < amount+1; i++) { 
            int cost = INT_MAX;
            for (int j = 0; j < coins.size(); j++) { 
                if (i - coins[j] >= 0) { // 如果dp[j - coins[i]]是初始值则跳过
                    cost = min(cost, res[i- coins[j]]+1);
                }                
            }
            res[i] = cost;
        }
        if (res[amount] == INT_MAX) return -1;
        return res[amount];
    }
};


int main() {
    Solution s1;
    vector<int>coins({ 1, 2, 5 });
    int amount = 11;
    int res = s1.coinChange(coins, amount);
    cout << res << endl;

    Solution002 s2;
    res = s2.coinChange(coins, amount);
    cout << res << endl;

	system("pause");
	return 0;
}







